A Write-friendly Store for SILT: Part II
Learn how to design a key-value store for fast writing.
Indexing for reduced per-key memory consumption#
Since this store contains the least amount of keys, the overall impact of using the hash table on per-key memory consumption will be low. However, since reduced per-key memory consumption is our goal, we should find ways to reduce the impact of the above hash table. We can reduce per-key memory used by the write-friendly store by:
Ensuring high occupancy of the hash table
Using a partial key instead of the full key
Partial-key cuckoo hashing for higher occupancy#
The technique we will use for hashing is partial-key cuckoo hashing. The partial-key means we will use a part of the key.
Hash functions#
Cuckoo hashing requires two hash functions, h1, and h2. Both map a key K to two candidate buckets, h1(K) and h2(K), on the same table.
Insertion algorithm#
To insert a new key, K1, we will compute its candidate buckets h1(K1) and h2(K1) and check if one, both, or none of the two buckets are empty.
If both buckets are empty, store
K1in one of the buckets.If one bucket is empty, check if
K1is stored in the occupied bucket.If
K1is already stored, update the offset.Otherwise, store
K1in the empty bucket.
If neither bucket is empty, check if
K1is stored in one of the occupied buckets.If
K1is already stored, update the offset.Otherwise,
K1displacesK2in one of theK1candidate buckets. We will insertK2into its other candidate bucket.If the other candidate bucket for
K2is empty, it is stored there.If the other candidate bucket is not empty,
K2displacesK3, which resides in its other candidate bucket.We will repeat the process in 3(II) for
K3until we find an empty bucket for a limited number of displacements. If we reach our allowed number of displacements and cannot find an empty bucket, we will initialize a new write-friendly store and store the displaced key in one of its candidate buckets in the new store.
1 of 8
2 of 8
3 of 8
4 of 8
5 of 8
6 of 8
7 of 8
8 of 8
We will repeat the process of displacing keys for a limited number of attempts. When that number is reached, we will initialize a new write-friendly store and move all entries in the current store to the next key-value store in the pipeline. From this point onwards, the new write-friendly store will cater to arriving PUT and DELETE requests. The configured limit of the number of keys displaced is our way of determining the level of occupancy we would want for our hash table. The number of displacements required to insert a key increases as the occupancy of the hash table increases and becomes very high in the late range (90%+). Based on our hardware and other configurations, we can determine an acceptable number of attempts before we declare the current write-friendly store too occupied to allow for an acceptable cost of inserts.
Let's look at how limiting the number of displacements works. In the example below, the number of allowed displacements to insert a key is 3.
1 of 10
2 of 10
3 of 10
4 of 10
5 of 10
6 of 10
7 of 10
8 of 10
9 of 10
10 of 10
Partial-key hashing#
We will save memory by not storing the entire key in the hash table. Instead, we will use a tag for each key in the hash table. We will mark a key's entry in the hash table with its tag by storing the tag along with its offset (position in the storage log). Every key-value entry in the write-friendly store will have the following:
Complete key and value in the storage log
Hash table entry containing:
The key's tag
The key's offset
We will compute each key's tag using a hash function and two non-overlapping key fragments from the lower-order bits of the key. Our two hash functions for cuckoo hashing essentially use only one hash function at the core but apply it to the two key fragments of a key.
To formalize, for a key K,
h1applies the hash function to the first key fragment to compute the index of the first candidate bucket of that key. We will denote this index ash1(K)for the keyK.h2does the same to the second key fragment to compute the index of the second candidate bucket. We will denote this index ash2(K)for the keyK.
While the technique above reduces per-key memory consumption, it raises a problem. For displacing a key and storing it in its alternate bucket, we require computing the index for the alternate bucket. We cannot do this without looking up the complete key stored in storage. If we look up a key for every displacement, this can result in multiple disk seeks/reads for a single PUT or DELETE request and, consequently, a higher read amplification.
We can overcome the above problem by storing the tag for the alternate bucket instead of the current bucket in which the key is stored. For example, we insert the key K1 into its candidate bucket h1(K1), then we will mark it with h2(K1). If we need to move K1 to its alternate bucket in the future, we do not need to compute h2(K1). Now, if we need to store another key, say K2 in h1(K1) since it is the second candidate bucket for K2; more specifically, h2(K2) equals h1(K1). Since we mark entries by their alternate bucket, we do not require to look up either key to compute the alternate bucket. We can locate h2(K1) because we have marked an entry for K1 with this tag. We will store K2 in h2(K2). Now we need to mark the K1 entry with the tag h1(K1):
If
K2is for a new request, meaning it is not itself being displaced by another key, then we will have values for both its candidate bucketsh1(K2)andh2(K2)from the initial computation of candidate buckets. In this case, we will use the value from the initial computation of candidate buckets for new requests and markK1withh2(K2)(which is also equal toh1(K1)) and markK2withh1(K2).If
K2is not a new request, meaning another key is displacing it, then it is marked withh2(K2)(equal toh1(K1)), and we will use this value to markK1. We will markK2with the tag on the key displacing it.
Let’s look at how this will look using our first displacement example.
1 of 4
2 of 4
3 of 4
4 of 4
Associativity#
We can improve occupancy by increasing the associativity of the cuckoo hash table, allowing us to store more than one entry in a single bucket.
A Write-friendly Store for SILT: Part I
A Write-friendly Store for SILT: Part III